\section{Maze Representation}
\label{sec:representation}

Ms. Pac-Man takes actions in the maze based on various conditions. The goal of Ms. Pac-Man is to score maximum points in the game by eating pills, power-pills, and edible ghosts. Ms. Pac-Man can move in four directions with respect to the maze (Up, Down, Left, and Right). To facilitate this translation, the algorithm uses an internal representation of the maze as a graph. Intersections in the maze are represented as nodes in the graph and a corridor in the maze, where movement is restricted by the walls to two possible directions, is represented as a pair of weighted directed edges in the graph. A graph is created from the maze by running walk algorithm over the junctions where you start from one junction and keep walking in all available direction in order to discover another junction and update edge in the graph based on discovered node. This graph is shown in the Figure~\ref{fig:mazeGraph}

\begin{figure}
  \begin{center}
    \includegraphics[width=0.45\textwidth]{figures/nodeFig}
    \caption{Generated Graph representation from Maze}
    \label{fig:mazeGraph}
  \end{center}
\end{figure} 

In this graph, intersection $3$ and intersection $4$ have two possible ways to connect, to remove ambiguity with different path, power pill at location $1$ consider as a junction and same with other power pill locations. In the absence of power pill, corners of the maze are considered as a junction. At each time iteration of game, ours Ms. Pac-Man agent called as HRTPacman take information from the Ms. Pac-Man vs Ghosts API to update its position in the graph. Junction graph created from maze contains position of Ms. Pac-Man as root node. At each time step, the graph is updated with Ms. Pac-Man location as root and perform decision making over the newly updated graph. 
We create the graph of junctions just once at the beginning of the game and in every game cycle the best move is computed for the PacMan. We use the current state of the game for finding the best moving direction for PacMan. The state of the game includes: number of pills, power pills, ghosts and edible ghosts. We consider the state of the game for the area near to the pacman and the paths that it can take by different moving direction. 

We use the Breadth First Search (BFS) algorithm for visiting the possible paths from PacMan. For applying the BFS we use the original graph which is created in the beginning of the game and find the immediate junctions to the pacman. The PacMan itself is considered as a node and connected to the immediate junctions which are the nodes of the graph. After visiting the immediate neighboring junctions we go one level further and visit the children of the first level. We continue this process up to the max level which is a parameter in our method. This parameter shows how much the pacman is predictive. If we only have one level the pacman is very greedy and just look at the immediate junctions, while in case we go through $k$ level the pacman will consider longer path and have better prediction about the future. 

In our implementation we check the visited junctions and do not visit them again. We assume that if a junction can be reached by pacman in a possible path it will be visited in smaller level in one branch of the BFS tree rather than be visited in higher level. Using this check we also make sure that we do not have cycle in the prediction. Because, if we have cycle on edge can be counted more than one time for a path which is not correct.

The score of the path is computed by the weighted summation of the total score along the path. The weight of the different entity in score function is evolved by GA and for each chromosome we have a set of weight. When a node of the graph is visited the score of the node from pacman to the node is the summation of the score up to the its parent node and the score of the edge between current node and parent node. The weight of different entity shows the importance of each one in decision making process.

Once the entire nodes in the BFS tree get visited, the node with maximum score is selected as the target. Then, we backtrack from the target to the root node which is the pacman and find the immediate movement direction that it should have for going toward target node. Sometimes, it happen that there are more than one target node with equal maximum score. In that case the one which is the same as previous move is selected as current move.

HRTPacman agent considers the weighted graph and take the edge of maximum weight as the next move in the game. Number of pill (P), Number of Power Pills (PP), Number of Ghost (G), and Number of Edible Ghost (EG) between two nodes in graph decides the weight of the edge. Edge weight is calculated as follows:

\begin{align*}
Weight_{Edge\left(i,j\right)} &= A \times P\left(i,j\right) \\
&+ B \times PP(i,j) \\
&- C \times G(i,j) \\
&+ D \times EG(i,j)
\end{align*}

Where $A$, $B$, $C$, $D$ are non-negative real number coefficients which are evolved by the genetic algorithm.  Above equation suggested the rewards and penalty associated with a particular edge in the graph. Number of pill, power pills, and edible ghost make positive weight and number of non-edible ghost on the edge reduce the importance of edge.  HRTPacman take turns decisions based on most appropriate neighboring edge on the graph. Algorithm for selecting edge is shown below: 
\begin{enumerate}
\item Convert Ms. Pac-Man location into the junction and add it in the graph.
\item Run BFS over the graph and explore the possible number of junctions that can be reached for K levels.
\item Update the weight of the edges along discovered paths Ps.
\item Find Max (Weight of Edge (Ps)) and return the next move require to walk on the maximum weighted path.
\end{enumerate}





\section{GA Learning}
\label{sec:learning}
A genetic algorithm is a search space optimization procedure where population of individuals is evaluated for fitness criteria and individuals with maximum fitness are selected for creating new population with exploited individuals as well as newly explored individuals using control parameters. This process continues until the optimal individual originated in the population are limited to a certain number of generations. Genetic algorithms are pseudo-random algorithm i.e. many runs required with similar control parameter settings for confirming the performance of the GA. Control parameters such as population size, crossover rate, mutation rate, and selection method require multiple run of different values for different problems. Genetic Algorithm performs the evolution of Edge weight coefficients $A$, $B$, $C$, and $D$. Each coefficient is $8$ bit long decimal value range from $0$-$127$. Individual chromosome in the population has a length of $32$ bits where $8$ bit for each coefficient. Fitness of the individual is the maximum game score earn by HRTPacman agent given coefficient individual from the population.

